package main

import (
	"math"
	"sort"
)

// 拍扁数组
func deleteAndEarn(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	data := make(map[int]int)
	lastNum := math.MaxInt8
	for _, n := range nums {
		data[n] = data[n] + n
		if n < lastNum {
			lastNum = n
		}
	}
	compressNums := make([]int, len(data))
	count := 0
	for k := range data {
		compressNums[count] = k
		count++
	}
	// 选择后需删除 +1 -1的数。其实就转换为 +1 -1 数的和当前数比较了.
	// 排序已方便转移方程
	sort.Ints(compressNums)
	sum := data[compressNums[0]]
	lastSum := 0
	for i := 1; i < len(compressNums); i++ {
		if compressNums[i] == compressNums[i-1]+1 { // 值相邻
			sum, lastSum = Max(data[compressNums[i]]+lastSum, sum), sum
		} else {
			sum, lastSum = data[compressNums[i]]+sum, sum
		}
	}
	return sum
}

func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	//deleteAndEarn([]int{3, 4, 2, 2, 3, 5, 5, 6, 6, 8, 9})
	deleteAndEarn([]int{3, 3, 3, 4, 2})
}
